﻿#pragma once
#include <ostream>

#include "FormatedUtil.h"
#include "Index.h"

class ILongestPositiveMultiOfSubArr
{
public:
	/**
	 * 乘积为正数的最长连续子数组.
	 * https://www.nowcoder.com/practice/0112b9b5a09048d89309f55ea666db91?tpId=230&tqId=2378149&ru=/exam/oj&qru=/ta/dynamic-programming/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D230
	 *
	 * 给定一个长度为 n 的整数数组，请你找出其中最长的乘积为正数的子数组长度。
	 * 子数组的定义是原数组中一定长度的连续数字组成的数组。
	 */
	virtual int getLongestPositiveMutliLengthOfSubArr(std::vector<int>& arr) = 0;
};
class LongestPositiveMultiOfSubArr
{
public:
	class DP:public ILongestPositiveMultiOfSubArr
	{
	public:
		int getLongestPositiveMutliLengthOfSubArr(std::vector<int>& arr) override
		{
			if (arr.empty())
				return 0;
			const int arrSize = arr.size();
			//最长乘积为正数的子数组长度
			int resultLen = 0;
			//遍历时以前一个元素为结尾的最长乘积为正数的子数组长度
			int positiveMultiLen = 0;
			//遍历时以前一个元素为结尾的最长乘积为负数的子数组长度
			int minusMultiLen = 0;

			for (int i = 0; i < arrSize; ++i)
			{
				if (arr[i] == 0)
				{
					minusMultiLen = positiveMultiLen = 0;
					continue;
				}
				//注意考虑首次positiveMultiLen和minusMultiLen从0开始变化的情况
				if (arr[i] > 0)
				{
					positiveMultiLen++;
					if (minusMultiLen > 0)
						minusMultiLen++;
				}
				else
				{
					const int newPositiveMultiLen = minusMultiLen > 0 ? minusMultiLen + 1 : 0;
					const int newMinusMultiLen = positiveMultiLen + 1;

					positiveMultiLen = newPositiveMultiLen;
					minusMultiLen = newMinusMultiLen;
				}
				//收集结果
				resultLen = std::max<>(positiveMultiLen, resultLen);
			}
			return resultLen;
		}
	};
};

